package ACM_Brush;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Map;

public class Solution146 {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        System.out.println("null");
        cache.put(1, 1);
        System.out.println("null");
        cache.put(2, 2);
        System.out.println("null");
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println("null");
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println("null");
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}

class LRUCache {
    private int capacity;
    private Map<Integer, Integer> map;
    // 对头表示最近未使用
    private LinkedList<Integer> queue;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            queue.remove(Integer.valueOf(key));
            queue.addLast(key);
            return map.get(key);
        } else
            return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            queue.remove(Integer.valueOf(key));
            queue.addLast(key);
        } else if (map.size() < capacity) {
            map.put(key, value);
            queue.addLast(key);
        } else {
            Integer first = queue.pollFirst();
            map.remove(first);
            map.put(key, value);
            queue.addLast(key);
        }
    }
}